#include <iostream>
#include <climits>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/system/basic.h>
#include "control.h"

#include <LEDA/core/p_queue.h>
#include <LEDA/graph/node_map.h>
#include <LEDA/graph/node_array.h>

using namespace leda;
using std::cout;
using std::endl;

#define DIRECTED false

/**
 * Get the weight of an edge
 */
int get_edge_weight(GraphWin & gw , edge e)
{
	string edge_label = gw.get_user_label(e);
	int weight = atoi(edge_label.c_str());
	return weight;
	//return atoi(gw.get_user_label(e).c_str());
}

/**
 * Get a random node form the graph
 */
node get_random_node(graph &g) {
	return g.first_node();
}

/**
 * Get proper priority by inversing the edge weight (or 0 if edge weight is 0)
 */
double get_priority(GraphWin &gw , edge &e ) {
	double weight = (double)get_edge_weight(gw , e);
	return weight;
//	if (weight == 0)
//		return 0;
//
//	return (double)1/weight;
}

/**
 * Prints the priorities of a priority queue
 */
void print_pq(p_queue<double, edge> pq) {
	cout <<"Printing PQ, size " << pq.size() << endl;
	while(!pq.empty())
	{
		cout << pq.del_min() << endl;
	}
	cout <<"Printing PQ END" << endl;
}

/**
 * Prim's algorithm to compute a MST in an undirected graph
 */
void prim(graph &g, GraphWin &gw)
{
	//store all pq_items for quick access for updates etc.
	node_array<bin_heap_item> node_pq_pointer(g , NULL);

	//marks the presence of a node in the tree
	node_array<bool> marker(g, false);

	//map from nodes in the pq to corresponding edges
	node_array<edge> node_edge_map(g , NULL);

	//pick a random start node
	node start = get_random_node(g);

	//Color the starting node
	gw.set_color(start , blue);

	//priority queue for all nodes adjacent to our tree
	p_queue<double, node> priority_queue;

	int current_mst_weight = 0;

	//number of nodes in our tree
	int counter = 1;

	bin_heap_item it = priority_queue.insert(0 , start);
	node_pq_pointer[start] = it;

	gw.set_color(start , green);
	control_wait(0.5);

	marker[start] = true;

	while(!priority_queue.empty() && counter <= g.number_of_nodes()) {
		//get next node and the corresponding edge
		node target = priority_queue.inf(priority_queue.find_min());
		edge current_edge = node_edge_map[target];

		gw.set_color(target , blue);

		// delete item from priority queue
		priority_queue.del_min();

		//at the starting node the edge will be NULL.
		if (current_edge != NULL) {

			//add the edge to the MST
			control_wait(0.5);
			gw.set_color(current_edge, blue);
			gw.set_width(current_edge, 3);
			gw.set_color(target, blue);
			gw.set_color(g.opposite(target, current_edge), blue);
			control_wait(0.5);

			//increase size of mst
			current_mst_weight += get_edge_weight(gw , current_edge);
		}

		// mark target as visited
		marker[target] = true;

		// we added a node to the tree, therefore we increase the node counter
		counter++;

		// unset the pointer from target to its pq_item (it is gone anyway)
		node_pq_pointer[target] = NULL;


		edge adj_edge;
		forall_inout_edges(adj_edge, target) {
			node neighbour = g.opposite(adj_edge, target);

			// ignore self-loops and nodes that are marked
			if ((neighbour != target) && (!marker[neighbour])) {
				// get the priority queue item.
				edge current_best_edge = node_edge_map[neighbour];

				// get the priority queue item.
				bin_heap_item pq_item = node_pq_pointer[neighbour];

				// if item exists check if we have to update it
				// else we add a new item to the list
				if (current_best_edge != NULL) {
					double new_weight = get_priority(gw , adj_edge);
					if (get_priority(gw , current_best_edge) > new_weight) {
						// replace the current edge with the 'better' edge
						priority_queue.change_inf(pq_item, neighbour);
						priority_queue.decrease_p(pq_item, new_weight);

						node_edge_map[neighbour] = adj_edge;

						//make new best edge for this node green
						gw.set_color(adj_edge , green);
						gw.set_color(neighbour , green); //not really needed, just making sure it is green..
						//make old best edge for this node red
						gw.set_color(current_best_edge , red);

					} else {
						//edge is not better than currently best edge, so we color it red.
						gw.set_color(adj_edge , red);
					}
					control_wait(2);
				} else {
					// if the node is not yet in our queue we add it
					// and add the reference in the node_pq_pointer map
					bin_heap_item new_item = priority_queue.insert(get_priority(gw , adj_edge), neighbour);
					node_edge_map[neighbour] = adj_edge;
					node_pq_pointer[neighbour] = new_item;

					// finally we color it to indicate that this is a adjacent edge
					// which will be considered in the next round
					gw.set_color(adj_edge , green);
					gw.set_color(neighbour , green);
					control_wait(1);
				}
			}
		}
	}

	gw.message("MST weight: " + string("%d" , current_mst_weight));


}


int main(int argc, char *argv[])
{
    GraphWin gw(800, 600);
    gw.display();
    create_control();
    // set environment to display a directed / undirected graph depending on the DIRECTED constant
    gw.set_directed(DIRECTED);
    if (argc > 1)
        gw.read(argv[1]);
    gw.edit();
    graph &g = gw.get_graph();
    if (g.number_of_nodes() == 0) {
        gw.close();
        destroy_control();
        exit(1);
    }

    // initialize graph nodes and edges as yellow
    node v;
    edge e;
    forall_nodes(v, g)
    {
        gw.set_label_type(v, user_label);
        gw.set_color(v, grey3);
    }
    forall_edges(e, g)
    {
        gw.set_color(e, grey3);
    }

    //run prim's algorithm
    prim(g, gw);

    gw.acknowledge("Ready!");
    gw.edit();
    gw.close();
    destroy_control();
    exit(0);
}
